package com.zyk.leetcode;

/**
 * @author zhangsan
 * @date 2021/4/6 15:25
 */
public class C2 {

    // https://leetcode-cn.com/problems/add-two-numbers/
    // 获取数值计算, 会出现数值越界问题
    public static ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        long ans = getValue(l1) + getValue(l2);
        // 构建这棵链表
        // 个 -> 十 -> 百 -> 千
        ListNode head = new ListNode((int) (ans % 10));
        ans /= 10;
        ListNode cur = head, next;
        while (ans != 0) {
            next = new ListNode((int) (ans % 10));
            ans /= 10;
            cur.next = next;
            cur = next;
        }
        return head;
    }

    public static long getValue(ListNode head) {
        long v = head.val;
        long digit = 10;
        ListNode cur = head.next;
        while (cur != null) {
            v += digit * cur.val;
            digit *= 10;
            cur = cur.next;
        }
        return v;
    }

    // 递归计算, 不必考虑数值越界问题
    public static ListNode addTwoNumbers2(ListNode l1, ListNode l2) {
        //   个 -> 十 -> 百
        //+  个 -> 十 -> 百
        return recur(l1, l2, 0);
    }

    public static ListNode recur(ListNode l1, ListNode l2, int carry) {
        if (l1 == null && l2 == null) {
            return carry == 0 ? null : new ListNode(carry);
        }
        ListNode cur;
        int sum;
        sum = (l1 == null ? 0 : l1.val) + (l2 == null ? 0 : l2.val) + carry;
        cur = new ListNode(sum % 10);
        cur.next = recur(l1 == null ? null : l1.next, l2 == null ? null : l2.next, sum > 9? 1: 0);
        return cur;
    }


    // for test
    public static ListNode generateList(int maxLen, boolean fixedSize) {
        maxLen = fixedSize ? maxLen : (int) (maxLen * Math.random() + 1);
        ListNode root = new ListNode((int) (Math.random() * 9 + 1));
        ListNode cur = root;
        int i = 1;
        while (i < maxLen) {
            cur.next = new ListNode((int) (Math.random() * 9 + 1));
            ;
            cur = cur.next;
            i++;
        }
        return root;
    }

    // for test
    public static void main(String[] args) {
        ListNode l1 = generateList(7, true);
        ListNode l2 = generateList(4, true);

        System.out.println(getValue(l1));
        System.out.println(getValue(l2));

        ListNode ans = addTwoNumbers(l1, l2);
        ListNode ans2 = addTwoNumbers2(l1, l2);
        while (ans != null) {
            System.out.print(ans.val);
            ans = ans.next;
        }
        System.out.println();
        while (ans2 != null) {
            System.out.print(ans2.val);
            ans2 = ans2.next;
        }
        System.out.println();
    }

}
